#include <deque>
#include <vector>
using namespace std;
// https://leetcode.cn/problems/sliding-window-maximum/?envType=study-plan-v2&envId=top-100-liked
class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        vector<int> reslut; // 存储滑动窗口的最大值结果
        deque<int> dq;      // 双端队列，用于存储当前窗口中可能的最大值的索引

        // 1. 初始化第一个窗口
        for (int i = 0; i < k; ++i)
        {
            // 保持队列中元素递减，如果当前元素比队尾元素大，则移除队尾元素
            while (!dq.empty() && nums[dq.back()] < nums[i]) // 必须使用while，因为可能有多个元素比当前元素小
            {
                dq.pop_back();
            }
            // 将当前元素的索引加入队列
            dq.push_back(i);
        }

        // 2. 将第一个窗口的最大值加入结果
        reslut.push_back(nums[dq.front()]);

        // 3. 遍历剩余的元素，滑动窗口
        for (int i = k; i < nums.size(); ++i)
        {
            // 3.1 如果队列头部的索引已经不在当前窗口范围内，移除它
            while (!dq.empty() && i - dq.front() + 1 > k) // i - dq.front() + 1 > k 说明窗口大小超过k 必须使用while
            {
                dq.pop_front();
            }

            // 3.2 保持队列中元素递减，如果当前元素比队尾元素大，则移除队尾元素
            while (!dq.empty() && nums[dq.back()] < nums[i])
            {
                dq.pop_back();
            }

            // 3.3 将当前元素的索引加入队列
            dq.push_back(i);

            // 3.4 将当前窗口的最大值加入结果
            reslut.push_back(nums[dq.front()]);
        }
        // 4. 返回结果
        return reslut; // 返回所有窗口的最大值
    }
};